/**
 * https://en.wikipedia.org/wiki/Longest_increasing_subsequence
 * 
 */


/**
 * 
 * @param {number[]} nums
 * @return {number[]} 
 */
function getSeq(nums) {
    let n = nums.length
    let p = new Array(n).fill(0)
    let m = new Array(n + 1).fill(0)
    let l = 0

    for (let i = 0; i < n; i++) {
        let lo = 1
        let hi = l + 1

        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo) / 2)
            if (nums[mid] < nums[i]) {
                lo = mid + 1
            } else {
                hi = mid
            }
        }
        // 赋值并交换
        let newL = lo
        p[i] = m[newL - 1]
        m[newL - 1] = i

        if (newL > l) {
            l = newL
        }
    }
    console.log()
    let s = []
    let k = m[l]
    for (let i = l - 1; i >= 0; i--) {
        s[i] = nums[k]
        k = p[k]
    }
    return s

}


console.log(getSeq([4, 3, 5, 0, 8, 4, 12, 2, 14]))